/// @tags:
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

namespace BlueQuantum {

int const N = 1e5 + 5;

int n, m, p, maxl;
int vis[N], tim, cnt[N], nxt[N], cir[N];
int t[1 << 18][60], add[1 << 18], tmp[60], mod[N];
bool tag[1 << 18];

inline void pushUp(int x) {
  t[x][0] = t[x << 1][0] + t[x << 1 | 1][0];
  if ((tag[x] = tag[x << 1] && tag[x << 1 | 1]))
    for (int i = 1; i < maxl; ++i) t[x][i] = t[x << 1][i] + t[x << 1 | 1][i];
}

inline void pushDown(int o, int l, int r) {
  if (add[o]) {
    if (l == r) {
      while (add[o]) t[o][0] = nxt[t[o][0]], add[o]--;
      if (cir[t[o][0]]) {
        tag[o] = true;
        for (int i = 1; i < maxl; ++i) t[o][i] = nxt[t[o][i - 1]];
      }
      return;
    }
    int mid = (l + r) >> 1;
    add[o << 1] += add[o], add[o << 1 | 1] += add[o];
    if (tag[o << 1]) {
      for (int i = 0; i < maxl; ++i) tmp[i] = t[o << 1][mod[add[o] + i]];
      memcpy(t[o << 1], tmp, sizeof(tmp));
    } else
      pushDown(o << 1, l, mid);
    if (tag[o << 1 | 1]) {
      for (int i = 0; i < maxl; ++i) tmp[i] = t[o << 1 | 1][mod[add[o] + i]];
      memcpy(t[o << 1 | 1], tmp, sizeof(tmp));
    } else
      pushDown(o << 1 | 1, mid + 1, r);
    add[o] = 0;
    pushUp(o);
  }
}

void built(int x, int l, int r) {
  if (l == r) {
    cin >> t[x][0];
    if (cir[t[x][0]]) {
      tag[x] = 1;
      for (int i = 1; i < maxl; ++i) t[x][i] = nxt[t[x][i - 1]];
    }
    return;
  }
  int mid = (l + r) >> 1;
  built(x << 1, l, mid), built(x << 1 | 1, mid + 1, r);
  pushUp(x);
}

void modify(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) {
    add[x]++;
    if (tag[x]) {
      for (int i = 0; i < maxl; ++i) tmp[i] = t[x][mod[i + 1]];
      memcpy(t[x], tmp, sizeof(tmp));
    } else
      pushDown(x, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  pushDown(x, l, r);
  if (L <= mid) modify(x << 1, l, mid, L, R);
  if (mid < R) modify(x << 1 | 1, mid + 1, r, L, R);
  pushUp(x);
}

int query(int o, int l, int r, int L, int R) {
  if (L <= l && r <= R) return t[o][0];
  int mid = (l + r) >> 1, res = 0;
  pushDown(o, l, r);
  if (L <= mid) res = query(o << 1, l, mid, L, R);
  if (mid < R) res += query(o << 1 | 1, mid + 1, r, L, R);
  return res;
}

inline int main() {
  cin >> n >> m >> p;
  for (int i = 0; i < p; ++i) nxt[i] = i * i % p;
  for (int i = 0, x, y; i < p; ++i) {
    for (++tim, x = i, y = 1; vis[x] != tim; x = nxt[x]) vis[x] = tim, cnt[x] = y++;
    if (maxl < y - cnt[x]) maxl = y - cnt[x];
    for (; !cir[x]; x = nxt[x]) cir[x] = true;
  }
  for (int i = 0; i <= m; ++i) mod[i] = i % maxl;
  built(1, 1, n);
  for (int opt, x, y; m; --m) {
    cin >> opt >> x >> y;
    switch (opt) {
      case 0:
        modify(1, 1, n, x, y);
        break;
      case 1:
        cout << query(1, 1, n, x, y) << '\n';
    }
  }
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("sqr.in", "r", stdin);
  freopen("sqr.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
